/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package hojadetrabajo7;
import java.util.Scanner;
/**
 * esta clase crea el arbol y mira la frecuencia de cada carater 
 * @author RAUL
 */
public class Hojadetrabajo7 {
    
     final static int NCHAR = 128; 
      int ingreso;



    static int[] freqCount(String text) {
        int freq[] = new int[NCHAR];

        for(int i=0; i<text.length(); i++)
            freq[text.charAt(i)]++;

        return freq;
    }



    static Arbol makeArbol(String text) {
    
        
    
        int freq[] = freqCount(text);
        Arbol root[] = new Arbol[NCHAR];
        int n = 0;
        for(char i=0; i<freq.length; i++)
            if(freq[i] != 0)
                root[n++] = new Hoja(i, freq[i]);
     
      
    
        while(n > 1) {
            int i0 = 0;    
            int i1 = 1;    
            if(root[i0].peso > root[i1].peso) {
                i0 = 1;
                i1 = 0;
            }
            for(int i=2; i<n; i++)
                if(root[i].peso< root[i0].peso) {
                    i1 = i0;
                    i0 = i;
                } else if(root[i].peso < root[i1].peso)
                    i1 = i;
    
                
    
            int peso = root[i0].peso + root[i1].peso;
            root[i0] = new Node(root[i0], root[i1], peso);
            for(int i=i1+1; i<n; i++)
                root[i-1] = root[i];
            n--;
        }
    
        return root[0];
    }

 static class Encoder {
      String[] codetable;

      Encoder(Code code) {
         codetable = code.table;
      }      

      public String encode(String text) {
         char[] input = text.toCharArray();
         String result = "";

         for (int i = 0; i < input.length; i++) {  
            result = result + codetable[input[i]];
         }
         
         return result;
      }
    }
    

    static class Parse {
        Arbol arbol;
        int siguiente;

        Parse(String s, int pos) {
            if(s.charAt(pos) == '*') {
    	          arbol = new Hoja('*',1); // REPLACE 
                siguiente = pos + 1;         // THIS CODE
            } else {
                arbol = new Hoja(s.charAt(pos+1), 0);
                siguiente = pos + 2;
            }
        }
    }

    
     static class Decoder {
      Arbol root; 
      Arbol pos;   
      
      Decoder(Arbol tree) {
         root = tree;
      }      

      public String decode(String text) {
         char[] input = text.toCharArray();
         String result = "";
         pos = root;

         for (int i = 0; i < input.length; i++) { 
            if (pos instanceof Node) {
               if (input[i] == '1')
                  pos = ((Node) pos).izq;
               if (input[i] == '0')
                  pos = ((Node) pos).dere;
            }
            if (pos instanceof Hoja) {
               result = result + ((Hoja) pos).ch;
               pos = root;
            }
         }

         return result;
      }
    }

     
      static void test(String text) {

        Arbol arbol = makeArbol(text);
        Code code = new Code(arbol);
        
        String stringForm = arbol.toString();

        System.out.println();
        System.out.println("Length of text: " + text.length());
        System.out.println("The tree is: " + stringForm);
       
        System.out.println("Reconstruction of the tree equals original: "
               + new Parse(stringForm,0).arbol.toString().equals(stringForm));
               
        Encoder encoder = new Encoder(code);
        Decoder decoder = new Decoder(arbol);
        

        System.out.println("decode( encode (text) ) == text: "
                + decoder.decode(encoder.encode(text)).equals(text));
    }
    /**
     * este metdo pide el ingreso de la cadena y crea el arbol de huffman 
       * @param args 
       */
    public static void main(String[] args) {
        
        Scanner valor = new Scanner(System.in);
        String texto; 
        // TODO code application logic here
        System.out.println("Bienvenidos al Arbol HUFFMAN");
        System.out.println("Ingrese una cadena de caracters");
        texto= valor.nextLine();
         test(texto);
         
    }
}
